题目
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
思路
具体思路是这样的，首先建立一个矩阵vector，它的下标分别代表总金额，对应下标内保存的元素为可以组成总金额的总方式，由题意可知dp[0]肯定是为1的，因为只有不用硬币一种方式可以达到总金额为0，所以首先将其赋值为1，然后就是更新dp的值，因为是要用提供的硬币来组成总金额，所以对每种硬币和当前的总金额进行对比，如果总金额大于当前的硬币的面值，那么代表可以通过将总金额减去当前硬币面值的那个总金额的所有组成方式再加上一个当前硬币的方式来组成新的组成方式，就是说dp[i]=dp[i]+dp[i-coin];因为是按照coins来进行遍历的，所以在之前的dp[i]的组成硬币中肯定是不包括当前的硬币的，所以可以直接加上之前的dp[i]而不会发生重复，第二项就是上面说的，几种加上这个新硬币之后也可以满足总金额的组成方式，因为是第一次遍历到这个硬币，所以它也肯定是不会发生重复的。所以更新方程就是dp[i]=dp[i]+dp[i-coin]，直到将所有硬币遍历完，代表考虑了所有的硬币，最后输出dp[amount]就可以了。
code
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1,0);
dp[0]=1;//
for(auto coin:coins){
for(int i=1;i<=amount;i++){
if(i>=coin) dp[i]=dp[i]+dp[i-coin];
}
}
return dp[amount];
}